#include<vector>
#include<algorithm>
using std::max;
using std::vector;


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() < 2) return 0;
        int haveProfit = -prices[0], noProfit = 0, oldHaveProfit;
        int n = prices.size();
        for (int i = 1; i < n; i++) {
            oldHaveProfit = haveProfit;
            haveProfit = max(haveProfit, noProfit - prices[i]);
            noProfit = max(oldHaveProfit + prices[i], noProfit);
        }
        return noProfit;
    }
};